package recfun
import common._

object Main {
  def main(args: Array[String]) {
    println("Pascal's Triangle")
    for (row <- 0 to 10) {
      for (col <- 0 to row)
        print(pascal(col, row) + " ")
      println()
    }
  }

  /**
   * Exercise 1
   */
  def pascal(c: Int, r: Int): Int = {
    if (c == 0) return 1;
    if (r == 0) return 0;
    
    pascal(c - 1, r - 1) + pascal(c, r - 1);
  }
  
  /*
   * val c = chars.head;
        c match {
          case '(' => balance(chars.tail, closingBracketsCount+1)
          case ')' => balance(chars.tail, closingBracketsCount-1)
          case n => balance(chars.tail, closingBracketsCount)
        }
   * */
  

  /**
   * Exercise 2
   */
  def balance(chars: List[Char]): Boolean = {
    def balance(chars: List[Char], closingBracketsCount : Int) : Boolean = {
      if (chars.isEmpty) {
        closingBracketsCount match {
          case 0 => true
          case n => false 
        }
      }
      else {
        if (closingBracketsCount < 0) false else {
        	balance(chars.tail, chars.head match {
        	case '(' => closingBracketsCount+1
        	case ')' => closingBracketsCount-1
        	case n => closingBracketsCount
        	})
        }
      }
    }
    balance(chars, 0);
  }

  /**
   * Exercise 3
   */
  def countChange(money: Int, coins: List[Int]): Int = {
    /*
     * @param numberOfVariantsSummator - counts number of ways to change the given amount of money
     * @param money - input ammount to change
     * @param coins - nominations to use
     * @return
     */
    def countChange(numberOfWaysSummator: Int, money: Int, coins: List[Int]): Int = {
      def countChangeUseHead(numberOfWaysSummator: Int, money: Int, headSummator: Int, coins: List[Int]): Int = {
        if (headSummator == money) numberOfWaysSummator + 1
        else {
          if (headSummator > money) numberOfWaysSummator
          else { /* headSum < money*/
            countChange(
                countChangeUseHead(numberOfWaysSummator, money, headSummator + coins.head, coins), 
                  money - headSummator, coins.tail)
          }
        } 
      }
      if (money == 0) numberOfWaysSummator + 1
      else {
        if (coins.isEmpty) numberOfWaysSummator
        else {
          countChangeUseHead(numberOfWaysSummator, money, 0, coins)
        }
      }
    }
    if (money == 0) 0 else countChange(0, money, coins)
  }
      
  def countChange2(money: Int, coins: List[Int]): Int = (money, coins) match {
     case (0, _) => 1
     case (money, _) if money < 0 => 0
     case (_, coins)  if coins.isEmpty => 0
     case (money, coins) => countChange2(money - coins.head, coins) + countChange2(money, coins.tail) 
  }
}
